package com.example.demo.leetcode.classics150;

/**
 * ******************************************************
 *
 * @author liugh9
 * @version 1.0
 * @classname _34有效的数独
 * @description
 * @date 2023/07/19 16:22
 * <p>
 * ******************************************************
 */
public class _34有效的数独 {


    /**
     *
     * 请你判断一个 9 x 9 的数独是否有效。只需要 根据以下规则 ，验证已经填入的数字是否有效即可。
     *
     * 数字 1-9 在每一行只能出现一次。
     * 数字 1-9 在每一列只能出现一次。
     * 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）
     * 左上到右下
     * 00-22 03-25 06-28
     * 30-22 33-25 36-28
     * 60-22 63-25 66-28
     *
     *
     * 注意：
     *
     * 一个有效的数独（部分已被填充）不一定是可解的。
     * 只需要根据以上规则，验证已经填入的数字是否有效即可。
     * 空白格用 '.' 表示。
     *
     * 示例 1：
     *
     *
     * 输入：board =
     * [["5","3",".",".","7",".",".",".","."]
     * ,["6",".",".","1","9","5",".",".","."]
     * ,[".","9","8",".",".",".",".","6","."]
     * ,["8",".",".",".","6",".",".",".","3"]
     * ,["4",".",".","8",".","3",".",".","1"]
     * ,["7",".",".",".","2",".",".",".","6"]
     * ,[".","6",".",".",".",".","2","8","."]
     * ,[".",".",".","4","1","9",".",".","5"]
     * ,[".",".",".",".","8",".",".","7","9"]]
     * 输出：true
     * 示例 2：
     *
     * 输入：board =
     * [["8","3",".",".","7",".",".",".","."]
     * ,["6",".",".","1","9","5",".",".","."]
     * ,[".","9","8",".",".",".",".","6","."]
     * ,["8",".",".",".","6",".",".",".","3"]
     * ,["4",".",".","8",".","3",".",".","1"]
     * ,["7",".",".",".","2",".",".",".","6"]
     * ,[".","6",".",".",".",".","2","8","."]
     * ,[".",".",".","4","1","9",".",".","5"]
     * ,[".",".",".",".","8",".",".","7","9"]]
     * 输出：false
     * 解释：除了第一行的第一个数字从 5 改为 8 以外，空格内其他数字均与 示例1 相同。 但由于位于左上角的 3x3 宫内有两个 8 存在, 因此这个数独是无效的。
     *
     *
     * [[".",".","5",".",".",".",".",".","."]
     * ,[".",".",".","8",".",".",".","3","."]
     * ,[".","5",".",".","2",".",".",".","."]
     * ,[".",".",".",".",".",".",".",".","."]
     * ,[".",".",".",".",".",".",".",".","9"]
     * ,[".",".",".",".",".",".","4",".","."]
     * ,[".",".",".",".",".",".",".",".","7"]
     * ,[".","1",".",".",".",".",".",".","."]
     * ,["2","4",".",".",".",".","9",".","."]]
     *
     *
     *
     * 提示：
     *
     * board.length == 9
     * board[i].length == 9
     * board[i][j] 是一位数字（1-9）或者 '.'
     *
     *
     * @param board
     * @return
     */
    public boolean isValidSudoku(char[][] board) {
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if (!isValid(board, i, j)) {
                    return false;
                }
            }
        }
        return true;
    }

    private boolean isValid(char[][] board, int i, int j) {
        // 横向
        char curr = board[i][j];
        if (curr != '.') {
            for (int k = 0; k < 8; k++) {
                if (board[i][k] == '.' || k == j) {
                    continue;
                }
                if (board[i][k] == curr) {
                    return false;
                }
            }
            // 纵向
            for (int k = 0; k < 8; k++) {
                if (board[k][j] == '.' || k == i) {
                    continue;
                }
                if (board[k][j] == curr) {
                    return false;
                }
            }
            // 3x3
            int p = i / 3;
            int q = j / 3;
            int start_i = p * 3;
            int start_j = q * 3;
            int end_i = start_i + 2;
            int end_j = start_j + 2;

            for (int k = start_i; k <= end_i; k++) {
                for (int l = start_j; l <= end_j; l++) {
                    if (board[k][l] == '.' || (k == i && l == j)) {
                        continue;
                    }
                    if (board[k][l] == curr) {
                        return false;
                    }
                }
            }
        }

        return true;
    }

}
